# -*- coding: utf-8 -*-

"""剑指 Offer II 068. 查找插入位置
给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

示例 4:
输入: nums = [1,3,5,6], target = 0
输出: 0

示例 5:
输入: nums = [1], target = 0
输出: 0

提示:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums 为无重复元素的升序排列数组
-10^4 <= target <= 10^4"""


class Solution:
    """在有序数组中查找小于或等于目标值的最大元素，二分法"""
    def searchInsert(self, nums, target: int) -> int:
        head, tail = 0, len(nums)-1
        if nums[head] > target:
            return 0
        
        if nums[tail] == target:
            return tail
        elif nums[tail] < target:
            return tail+1

        while tail-head > 1:
            midd = (head+tail)//2
            if nums[midd] <= target:
                head = midd
            else:
                tail = midd
        
        if nums[head] == target:
            return head
        else:
            return head+1


if __name__ == '__main__':
    so = Solution()
    print(so.searchInsert(nums = [1,3,5,6], target = 5))
    print(so.searchInsert(nums = [1,3,5,6], target = 2))
    print(so.searchInsert(nums = [1,3,5,6], target = 7))
    print(so.searchInsert(nums = [1,3,5,6], target = 0))
    print(so.searchInsert(nums = [1], target = 0))

